//
//  BinarySearch.cpp
//  labuladong
//
//  Created by 刘振舟 on 2024/2/4.
//

#include "BinarySearch.hpp"

int binarySearchWithBound(vector<int> &nums, int target, bool isLeftBound) {
    int left = 0, right = nums.size() - 1;
    int ans = -1, middle;
    while (left <= right) {
        middle = left + ((right - left) >> 1);
        if (isLeftBound) {
            if (nums[middle] >= target) {
                ans = middle;
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        } else {
            if (nums[middle] <= target) {
                ans = middle;
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
    }
    return ans;
}

vector<int> Solution::searchRange(vector<int> &nums, int target) { 
    int leftBoundIndex = binarySearchWithBound(nums, target, true);
    int rightBoundIndex = binarySearchWithBound(nums, target, false);
    if (leftBoundIndex > rightBoundIndex || leftBoundIndex < 0 || rightBoundIndex == nums.size()) {
        return {-1, -1};
    } else {
        return {leftBoundIndex, rightBoundIndex};
    }
}
